package it.luigiarpino.kernighanLin.bipartition;

import java.util.HashSet;
import java.util.Set;

/**
 * 
 * @author Luigi Lorenzo Arpino
 * 
 * Assegnata una matrice restituisce una soluzione ottima al 
 * problema di bipartizionamento
 *
 */
public class LKBipartition
{
	
	private int[][] matrix;
	
	private int[] partitionA;
	private int[] partitionB;
	private int costo;
	
	
	public LKBipartition(int[][] matrice, int[] partA, int[] partB)
	{
		this.matrix=matrice;
		this.partitionA=getNewVettore( partA );
		this.partitionB=getNewVettore( partB );
		// Fas1 
		LKphase1 phase1=new LKphase1(matrix, partitionA, partitionB);
		int G = phase1.getGain();
		int[] partX = phase1.getSetX();
		int[] partY = phase1.getSetY();
		if (G > 0 )
		{
			do
			{
				// Sposto X in B ed Y in A
				Set<Integer> setA = getSet(partitionA);
				Set<Integer> setB = getSet(partitionB);
				removeElement(setA, partX);
				removeElement(setB, partY);
				addElement(setA, partY);
				addElement(setB, partX);
				// ripeto  la fase 1
				partitionA=getVettore(setA);
				partitionB=getVettore(setB);
				phase1=new LKphase1(matrix, partitionA , partitionB);
				G = phase1.getGain();
				partX = phase1.getSetX();
				partY = phase1.getSetY();
			}while(G>0);
		}
		else
		{
			// Ho finito
		}
		// calcolo il costo
		this.calcolaCosto();
	}
	
	private int[] getNewVettore(int[] vett)
	{
		int[] result=new int[vett.length];
		for (int i=0;i<vett.length;i++)
		{
			result[i]=vett[i];
		}
		return result;
	}
	
	private void removeElement(Set<Integer> set, int[] vettore)
	{
		for (int i=0 ; i< vettore.length ; i++)
		{
			set.remove(new Integer(vettore[i]));
		}
	}
	
	private void addElement(Set<Integer> set, int[] vettore)
	{
		for (int i=0;i< vettore.length ; i++)
		{
			set.add(new Integer(vettore[i]));
		}
	}
	
	
	private Set<Integer> getSet(int[] vettore)
	{
		Set<Integer> set=new HashSet<Integer>();
		for (int i=0;i< vettore.length ; i++)
		{
			set.add(new Integer(vettore[i]));
		}
		return set;
	}
	
	private int[] getVettore(Set<Integer> set)
	{
		int[]result=new int[set.size()];
		int i=0;
		for(Object object: set.toArray() )
		{
			int value=((Integer)object).intValue();
			result[i]=value;
			i++;
		}
		return result;
	}
	
	public int[] getPartitionA()
	{
		return this.partitionA;
	}
	
	public int[] getPartitionB()
	{
		return this.partitionB;
	}
	
	/**
	 * Calcola il costo delle partizioni
	 */
	private void calcolaCosto()
	{
		this.costo = 0;
		for (int i=0 ; i <partitionA.length ; i++)
		{
			for(int j=0 ; j< partitionB.length ; j++ )
			{
				int a=partitionA[i];
				int b=partitionB[j];
				int wab=matrix[a][b];
				costo += wab; 
			}
		}
	}
	
	public int getCosto()
	{
		return this.costo;
	}
	
	/*
	private void printSet(Set<Integer> set, String description)
	{
		System.out.println("\n"+description);
		for(Object object: set.toArray() )
		{
			int value =((Integer)object).intValue();
			System.out.print(" "+value);
		}
	}
	*/
	
	/*
	private void stampaPartioni()
	{
		System.out.println();
		System.out.println("Partizione A:");
		for(int i=0 ;i<partitionA.length; i++)
		{
			System.out.print(" "+partitionA[i]);
		}
		System.out.println();
		System.out.println("Partizione B:");
		for(int i=0 ;i<partitionB.length; i++)
		{
			System.out.print(" "+partitionB[i]);
		}
	}
	*/
	
	public static void main(String[] args)
	{
		/*
		int[][] matrix={
				   //0  1  2  3  4  5  
					{0, 0, 0, 0, 1, 0 },// 0
					{0, 0, 0, 0, 0, 1 },// 1
					{0, 0, 0, 0, 1, 0 },// 2
					{0, 0, 0, 0, 0, 1 },// 3
					{1, 0, 1, 0, 0, 1 },// 4
					{0, 1, 0, 1, 1, 0 },// 5
			};
		*/
		
		/*
		int[][] matrix={
			    //   0  1  2  3  4  5  6  7
					{0, 0, 1, 0, 0, 0, 0, 0 },// 0
					{0, 0, 1, 0, 0, 0, 0, 0 },// 1
					{1, 1, 0, 1, 1, 0, 0, 0 },// 2
					{0, 0, 1, 0, 0, 0, 0, 0 },// 3
					{0, 0, 1, 0, 0, 1, 1, 1 },// 4
					{0, 0, 0, 0, 1, 0, 0, 0 },// 5
					{0, 0, 0, 0, 1, 0, 0, 0 },// 6
					{0, 0, 0, 0, 1, 0, 0, 0 },// 7
			};
			*/
		int[][] matrix={
			    //   0  1  2  3 
					{0, 0, 1, 0},//0
					{0, 0, 1, 0},//1
					{1, 1, 0, 1},//2
					{0, 0, 1, 0},//3
			};
		LKBipartition lk=new LKBipartition(matrix,new int[]{0,1},new int[]{2,3});
		int[] partA=lk.getPartitionA();
		int[] partB=lk.getPartitionB();
		int costo=lk.getCosto();
		
		System.out.println();
		System.out.println("costo="+costo);
		System.out.println();
		System.out.println("Partition A");
		for(int i=0; i< partA.length ; i++)
	    {
			System.out.print(" "+partA[i]);
	    }
		System.out.println();
		System.out.println("Partition B");
		for(int i=0; i< partB.length ; i++)
	    {
			System.out.print(" "+partB[i]);
	    }
		
		
		
	}
	
	
}
